{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The k-th Lexicographical String of All Happy Strings of Length n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getHappyString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #长度为 n 的开心字符串中字典序第 k 小的字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个 「开心字符串」定义为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>仅包含小写字母&nbsp;<code>[&#39;a&#39;, &#39;b&#39;, &#39;c&#39;]</code>.</li>\n",
    "\t<li>对所有在&nbsp;<code>1</code>&nbsp;到&nbsp;<code>s.length - 1</code>&nbsp;之间的&nbsp;<code>i</code>&nbsp;，满足&nbsp;<code>s[i] != s[i + 1]</code>&nbsp;（字符串的下标从 1 开始）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>比方说，字符串&nbsp;<strong>&quot;abc&quot;</strong>，<strong>&quot;ac&quot;，&quot;b&quot;</strong> 和&nbsp;<strong>&quot;abcbabcbcb&quot;</strong>&nbsp;都是开心字符串，但是&nbsp;<strong>&quot;aa&quot;</strong>，<strong>&quot;baa&quot;</strong>&nbsp;和&nbsp;<strong>&quot;ababbc&quot;</strong>&nbsp;都不是开心字符串。</p>\n",
    "\n",
    "<p>给你两个整数 <code>n</code>&nbsp;和 <code>k</code>&nbsp;，你需要将长度为 <code>n</code>&nbsp;的所有开心字符串按字典序排序。</p>\n",
    "\n",
    "<p>请你返回排序后的第 k 个开心字符串，如果长度为 <code>n</code>&nbsp;的开心字符串少于 <code>k</code>&nbsp;个，那么请你返回 <strong>空字符串</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 1, k = 3\n",
    "<strong>输出：</strong>&quot;c&quot;\n",
    "<strong>解释：</strong>列表 [&quot;a&quot;, &quot;b&quot;, &quot;c&quot;] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 &quot;c&quot; 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 1, k = 4\n",
    "<strong>输出：</strong>&quot;&quot;\n",
    "<strong>解释：</strong>长度为 1 的开心字符串只有 3 个。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3, k = 9\n",
    "<strong>输出：</strong>&quot;cab&quot;\n",
    "<strong>解释：</strong>长度为 3 的开心字符串总共有 12 个 [&quot;aba&quot;, &quot;abc&quot;, &quot;aca&quot;, &quot;acb&quot;, &quot;bab&quot;, &quot;bac&quot;, &quot;bca&quot;, &quot;bcb&quot;, &quot;cab&quot;, &quot;cac&quot;, &quot;cba&quot;, &quot;cbc&quot;] 。第 9 个字符串为 &quot;cab&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2, k = 7\n",
    "<strong>输出：</strong>&quot;&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 10, k = 100\n",
    "<strong>输出：</strong>&quot;abacbabacb&quot;\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-k-th-lexicographical-string-of-all-happy-strings-of-length-n](https://leetcode.cn/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-k-th-lexicographical-string-of-all-happy-strings-of-length-n](https://leetcode.cn/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n3', '1\\n4', '3\\n9']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generate(self, n_want: int, hs: List[str], n_to_gen: List[int]) -> bool:\n",
    "        if n_want == 0:\n",
    "            n_to_gen[0] -= 1\n",
    "            return n_to_gen[0] == 0\n",
    "\n",
    "        for cand in \"abc\":\n",
    "            if len(hs) == 0 or hs[-1] != cand:\n",
    "                hs.append(cand)\n",
    "                if self.generate(n_want - 1, hs, n_to_gen):\n",
    "                    return True\n",
    "                hs.pop()\n",
    "            \n",
    "        return False\n",
    "\n",
    "\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        hs: List[str] = []\n",
    "        return \"\".join(hs) if self.generate(n, hs, [k]) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "TABLE = {'a':('b', 'c'), 'b':('a', 'c'), 'c':('a', 'b')}\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        n -= 1\n",
    "        i, rest = divmod(k - 1, 1 << n)\n",
    "        if i > 2:\n",
    "            return ''\n",
    "        # 第一个字符\n",
    "        ans = 'abc'[i]\n",
    "        # 剩下的字符，只有长度大于1才需要\n",
    "        if n:\n",
    "            for c in f'{rest:0{n}b}':\n",
    "                ans += TABLE[ans[-1]][int(c)]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        base = 2**(n-1)\n",
    "        res = ''\n",
    "\n",
    "        if k > base*3:\n",
    "            return \"\"\n",
    "\n",
    "        # 首字母 三种情况\n",
    "        level = ((k-1) // base) if k else 0\n",
    "        res += 'abc'[level]\n",
    "        base *= level\n",
    "        \n",
    "        # 其余字母 两种情况\n",
    "        for i in range(2, n+1):\n",
    "            temp = 2**(n-i)\n",
    "            if k > base+temp:\n",
    "                base += temp\n",
    "                res += 'b' if res[-1] == 'c' else 'c'\n",
    "            else:\n",
    "                res += 'b' if res[-1] == 'a' else 'a'\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "TABLE = {'a':('b', 'c'), 'b':('a', 'c'), 'c':('a', 'b')}\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        n -= 1\n",
    "        # 按首字母分为3部分，每部分的大小\n",
    "        part = 1 << n\n",
    "        # 第一个字符与剩下字符的编号，这个编号和二进制有极大的关系\n",
    "        i, rest = divmod(k - 1, part)\n",
    "        if i > 2:\n",
    "            return ''\n",
    "        # 第一个字符\n",
    "        ans = 'abc'[i]\n",
    "\n",
    "        if n:\n",
    "            for c in f'{rest:0{n}b}':\n",
    "                ans += TABLE[ans[-1]][int(c)]\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        base = 2 ** (n-1)\n",
    "        res = ''\n",
    "\n",
    "        if k > base * 3:\n",
    "            return ''\n",
    "\n",
    "        # 首字母 三种情况\n",
    "        level = ((k - 1) // base)\n",
    "        res += 'abc'[level]\n",
    "        base *= level\n",
    "        \n",
    "        # 其余字母 两种情况\n",
    "        for i in range(2, n + 1):\n",
    "            temp = 2 ** (n - i)\n",
    "            if k > base + temp:\n",
    "                base += temp\n",
    "                res += 'b' if res[-1] == 'c' else 'c'\n",
    "            else:\n",
    "                res += 'b' if res[-1] == 'a' else 'a'\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\tdef getHappyString0(self, n: int, k: int) -> str:\r\n",
    "\t\t'''Brute-Force Recurse'''\r\n",
    "\t\tif k > 3 * (2 ** (n - 1)):\r\n",
    "\t\t\treturn ''\r\n",
    "\t\t# Options under specific prefix\r\n",
    "\t\toptions = {'a': 'bc', \r\n",
    "\t\t\t\t\t'b': 'ac', \r\n",
    "\t\t\t\t\t'c': 'ab', \r\n",
    "\t\t\t\t\t'': 'abc'\r\n",
    "\t\t\t\t\t}\r\n",
    "\t\tres = set()\r\n",
    "\t\tdef recurse(curS):\r\n",
    "\t\t\t# cur: current fixed prefix string\r\n",
    "\t\t\tif len(curS) == n:\r\n",
    "\t\t\t\tres.add(''.join(curS))\r\n",
    "\t\t\t\treturn\r\n",
    "\t\t\tkey = curS[-1] if curS else ''\r\n",
    "\t\t\tfor char in options[key]:\r\n",
    "\t\t\t\trecurse(curS + char)\r\n",
    "\t\t\treturn\r\n",
    "\r\n",
    "\t\trecurse(str())\r\n",
    "\t\treturn sorted(res)[k - 1]\r\n",
    "\r\n",
    "\tdef getHappyString(self, n: int, k: int) -> str:\r\n",
    "\t\tik = k - 1 # let k be index start from 0\r\n",
    "\t\tnum_body = 2 ** (n - 1) # num of happystrs after prefix\r\n",
    "\t\tif ik + 1 > 3 * num_body: # Impossible\r\n",
    "\t\t\treturn \"\"\r\n",
    "\t\t\r\n",
    "\t\tres = \"\"\r\n",
    "\t\t# Options under specific prefix\r\n",
    "\t\toptions = {'a': ['b', 'c'], \r\n",
    "\t\t\t\t\t'b': ['a', 'c'], \r\n",
    "\t\t\t\t\t'c': ['a', 'b'], \r\n",
    "\t\t\t\t\t\"\": ['a', 'b', 'c']\r\n",
    "\t\t\t}\r\n",
    "\t\twhile num_body > 0:\r\n",
    "\t\t\tpre_idx = ceil((ik + 1) / num_body) - 1 # index of prefix\r\n",
    "\t\t\tres += options.get(res[-1] if res else res)[pre_idx] # res could be ''\r\n",
    "\t\t\tik %= num_body # new index `k` upder new prefix\r\n",
    "\t\t\tnum_body //= 2 # halve num of happystrs upder new prefix\r\n",
    "\r\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def getHappyString(self, n: int, k: int) -> str:\n",
    "        for i in itertools.product('abc', repeat=n):\n",
    "            s = ''.join(i)\n",
    "            if all(j*2 not in s for j in 'abc'):\n",
    "                 k -= 1\n",
    "            if k==0:\n",
    "                 return s\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            v = 2 ** (n - i - 1)\n",
    "            if i == 0:\n",
    "                if k > 3 * v:\n",
    "                    return \"\"\n",
    "                if k > 2 * v:\n",
    "                    ans.append(\"c\")\n",
    "                    k -= 2 * v\n",
    "                elif k > v:\n",
    "                    ans.append(\"b\")\n",
    "                    k -= v\n",
    "                else:\n",
    "                    ans.append(\"a\")\n",
    "            else:\n",
    "                if k > v:\n",
    "                    if ans[-1] == \"a\" or ans[-1] == \"b\":\n",
    "                        ans.append(\"c\")\n",
    "                    else:\n",
    "                        ans.append(\"b\")\n",
    "                    k -= v\n",
    "                else:\n",
    "                    if ans[-1] == \"b\" or ans[-1] == \"c\":\n",
    "                        ans.append(\"a\")\n",
    "                    else:\n",
    "                        ans.append(\"b\")\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "TABLE = {'a':('b', 'c'), 'b':('a', 'c'), 'c':('a', 'b')}\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        # 按首字母分为3部分，每部分的大小\n",
    "        part = 1 << n - 1\n",
    "        # 第一个字符与剩下字符的编号，这个编号和二进制有极大的关系\n",
    "        i, rest = divmod(k-1, part)\n",
    "        if i > 2:\n",
    "            return ''\n",
    "        # 第一个字符\n",
    "        ans = 'abc'[i]\n",
    "\n",
    "        if n > 1:\n",
    "            for c in f'{rest:0{n - 1}b}':\n",
    "                ans += TABLE[ans[-1]][int(c)]\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        all = 3 * 2 ** (n - 1)\n",
    "        if k > all:\n",
    "            return \"\"\n",
    "        first = (k - 1) // (2 ** (n - 1))\n",
    "        next = (k - 1) % (2 ** (n - 1))\n",
    "        ans = list()\n",
    "        if first == 0:\n",
    "            ans.append(\"a\")\n",
    "        elif first == 1:\n",
    "            ans.append(\"b\")\n",
    "        else:\n",
    "            ans.append(\"c\")\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            if ans[-1] == \"a\":\n",
    "                if next & 1 << i:\n",
    "                    ans.append(\"c\")\n",
    "                else:\n",
    "                    ans.append(\"b\")\n",
    "            elif ans[-1] == \"b\":\n",
    "                if next & 1 << i:\n",
    "                    ans.append(\"c\")\n",
    "                else:\n",
    "                    ans.append(\"a\")\n",
    "            else:\n",
    "                if next & 1 << i:\n",
    "                    ans.append(\"b\")\n",
    "                else:\n",
    "                    ans.append(\"a\")\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "TABLE = {'a':('b', 'c'), 'b':('a', 'c'), 'c':('a', 'b')}\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        n -= 1\n",
    "        i, rest = divmod(k - 1, 1 << n)\n",
    "        if i > 2:\n",
    "            return ''\n",
    "        # 第一个字符\n",
    "        ans = 'abc'[i]\n",
    "        # 剩下的字符，只有长度大于1才需要\n",
    "        if n:\n",
    "            for c in f'{rest:0{n}b}':\n",
    "                ans += TABLE[ans[-1]][int(c)]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        if k > 3 * 2 ** (n-1):  # 如果 k 超出数量限制，直接返回空字符串\n",
    "            return ''\n",
    "\n",
    "        k = k - 1  # 数字 -1\n",
    "        number_char = str(k // 2 ** (n - 1))  # 特殊处理第一个字符\n",
    "        k = k % 2 ** (n - 1)  # 取余数，进行后续操作\n",
    "        \n",
    "        if len(number_char) != n:  # 如果当前字符串长度不为 n ，就需要添加后续工作\n",
    "            number_char += '0' * (n - len(bin(k)[2:]) - 1) + bin(k)[2:]\n",
    "\n",
    "        # 此时，number_char 构建完成，其为一个类似二进制的字符串,例如：\n",
    "        # n = 5, k = 9, munber_char = '01000'\n",
    "        # n = 5, k = 8, munber_char = '00111'\n",
    "        # n = 3, k = 12, munber_char = '211'\n",
    "        #print(number_char)\n",
    "\n",
    "        res = ''\n",
    "        last = None\n",
    "        for cur in number_char:  # 根据 number_char 构建返回的字符串\n",
    "            last = get_0_or_1(cur,last)\n",
    "            res += last\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "def get_0_or_1(cur,last):  # 这个过程可能有点跳跃，具体可以参考最后一个图中的 蓝字部分\n",
    "\n",
    "    if last == 'a':\n",
    "        return 'b' if cur =='0' else 'c'\n",
    "\n",
    "    if last == 'b':\n",
    "        return 'a' if cur == '0' else 'c'\n",
    "\n",
    "    if last == 'c':\n",
    "        return 'a' if cur == '0' else 'b'\n",
    "\n",
    "    if last is None:  # 特殊处理第一位\n",
    "        return {\n",
    "            '0':'a',\n",
    "            '1':'b',\n",
    "            '2':'c'\n",
    "        }[cur]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = []\n",
    "        self.path = []\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        self.backtracking(['a', 'b', 'c'], n)\n",
    "        if k > len(self.result):\n",
    "            return \"\"\n",
    "        return self.result[k - 1]\n",
    "\n",
    "    def backtracking(self, characters, n):\n",
    "        if len(self.path) == n:\n",
    "            self.result.append(''.join(self.path))\n",
    "            return\n",
    "        for i in range(3):\n",
    "            if len(self.path) == 0:\n",
    "                self.path.append(characters[i])                \n",
    "            else:\n",
    "                character = self.path[-1]\n",
    "                if characters[i] == character:\n",
    "                    continue\n",
    "                else:\n",
    "                    self.path.append(characters[i])\n",
    "            self.backtracking(characters, n)\n",
    "            self.path.pop()\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        m = 3*(2**(n-1))\n",
    "        t = [\"a\",\"b\",\"c\"]\n",
    "        if k>m:\n",
    "            return \"\"\n",
    "        ans = \"\"\n",
    "        if k<=2**(n-1):\n",
    "            ans = ans+\"a\"\n",
    "        elif k<=2**n:\n",
    "            ans = ans+\"b\"\n",
    "            k -= 2**(n-1)\n",
    "        else:\n",
    "            ans = ans+\"c\"\n",
    "            k -= 2**(n)\n",
    "        if k<=3 and n==1:\n",
    "            return ans\n",
    "        pre = ans\n",
    "        n -= 1\n",
    "        while n>=1:\n",
    "            if k>2**(n-1):\n",
    "                k -= 2**(n-1)\n",
    "                for i in range(2,-1,-1):\n",
    "                    if t[i]!=pre:\n",
    "                        ans = ans+t[i]\n",
    "                        pre = t[i]\n",
    "                        break\n",
    "            else:\n",
    "                for i in range(3):\n",
    "                    if t[i]!=pre:\n",
    "                        ans = ans+t[i]\n",
    "                        pre = t[i]\n",
    "                        break\n",
    "            n-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        record = ['a', 'b', 'c'] #长为1的三个子串\n",
    "        i = 1\n",
    "        while i<n:\n",
    "            post = []\n",
    "            for s in record:\n",
    "                if s[-1]=='a':\n",
    "                    post.append(s+'b')\n",
    "                    post.append(s+'c')\n",
    "                elif s[-1]=='b':\n",
    "                    post.append(s+'a')\n",
    "                    post.append(s+'c')\n",
    "                else:\n",
    "                    post.append(s+'a')\n",
    "                    post.append(s+'b')\n",
    "\n",
    "            record=post\n",
    "            i += 1\n",
    "\n",
    "        if len(record) < k:\n",
    "            return \"\"\n",
    "        else:\n",
    "            return record[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        charset = ['a', 'b', 'c']\n",
    "        cnt = 0\n",
    "        ans = \"\"\n",
    "        path = []\n",
    "        def dfs(m):\n",
    "            nonlocal cnt, ans\n",
    "            if m == n:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    ans = \"\".join(path[:])\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            for i in range(len(charset)):\n",
    "                if (len(path) >= 1 and\n",
    "                    charset[i] == path[-1]):\n",
    "                    continue\n",
    "                path.append(charset[i])\n",
    "                if dfs(m + 1):\n",
    "                    return True\n",
    "                path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        def backtrack(pre,res):\n",
    "            nonlocal cnt,kthHappyString\n",
    "            if cnt >= k:\n",
    "                return\n",
    "            elif len(res) == n:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    kthHappyString = \"\".join(res)\n",
    "            else:\n",
    "                for ch in ('a','b','c'):\n",
    "                    if ch != pre:\n",
    "                        res.append(ch)\n",
    "                        backtrack(ch,res)\n",
    "                        res.pop()\n",
    "\n",
    "        total = 3 * (1 << (n - 1))\n",
    "        if k > total:\n",
    "            return \"\"\n",
    "        kthHappyString = \"\"\n",
    "        cnt = 0\n",
    "        backtrack(\"\",[])\n",
    "        return kthHappyString"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        if k>3*2**(n-1):\n",
    "            return \"\"\n",
    "        else:\n",
    "            d={\"a\":0,\"b\":1,\"c\":2}\n",
    "            e={0:\"a\",1:\"b\",2:\"c\"}\n",
    "            a=deque()\n",
    "            result=[\"\"]\n",
    "            k-=1\n",
    "            while n-1:\n",
    "                b=k%2\n",
    "                k=k//2\n",
    "                a.append(b)\n",
    "                n-=1\n",
    "            a.append(k)\n",
    "            while a:\n",
    "                c=a.pop()\n",
    "                if c>=d.get(result[-1],4):\n",
    "                    c+=1\n",
    "                result.append(e[c])\n",
    "        return \"\".join(result[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        res = ''\n",
    "        k -= 1\n",
    "        abc = 'abc'\n",
    "        maps = {'a':('b','c'), 'b':('a','c'), 'c':('a','b')}\n",
    "        i = 0\n",
    "        if k >= 3 * (1 << (n-1)):\n",
    "            return ''\n",
    "        while i < n:       \n",
    "            cnt = 1 << (n-i-1)\n",
    "            x, y = k // cnt, k % cnt\n",
    "            print(k, cnt, x, y)\n",
    "            if i == 0:\n",
    "                res += abc[x]\n",
    "            else:\n",
    "                res += maps[res[-1]][x]\n",
    "            k = y\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        ans = ''\n",
    "        def dfs(index,stack):\n",
    "            nonlocal k,ans\n",
    "            if ans:\n",
    "                return\n",
    "            if index == n and k == 1:\n",
    "                #print(f'第{k}次 {stack}')\n",
    "                ans = ''.join(stack)\n",
    "                return\n",
    "            if index == n:\n",
    "                #print(f'第{k}次 {stack}')\n",
    "                k -= 1\n",
    "                return \n",
    "           \n",
    "            for s in 'abc':\n",
    "                if stack and stack[-1] == s:\n",
    "                    continue\n",
    "                dfs(index+1,stack+[s])\n",
    "           \n",
    "        dfs(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        res = ''\n",
    "        k -= 1\n",
    "        abc = 'abc'\n",
    "        maps = {'a':('b','c'), 'b':('a','c'), 'c':('a','b')}\n",
    "        i = 0\n",
    "        if k >= 3 * (1 << (n-1)):\n",
    "            return ''\n",
    "        while i < n:       \n",
    "            cnt = 1 << (n-i-1)\n",
    "            x, y = k // cnt, k % cnt\n",
    "            # print(k, cnt, x, y)\n",
    "            if i == 0:\n",
    "                res += abc[x]\n",
    "            else:\n",
    "                res += maps[res[-1]][x]\n",
    "            k = y\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        if k > 3 * (2 ** (n - 1)):\n",
    "            return ''\n",
    "        \n",
    "        s = ['a', 'b', 'c']\n",
    "        t = 'abc'\n",
    "        i = 1\n",
    "        for _ in range(n - 1):\n",
    "            ss = []\n",
    "            for c in s:\n",
    "                for ch in t:\n",
    "                    if c[-1] != ch:\n",
    "                        ss.append(c + ch)\n",
    "            # print(ss)\n",
    "            s = ss\n",
    "\n",
    "    \n",
    "        return sorted(s)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        base = 2**(n-1)\n",
    "        res = ''\n",
    "\n",
    "        if k > base*3:\n",
    "            return \"\"\n",
    "\n",
    "        # 首字母 三种情况\n",
    "        level = ((k-1) // base) if k else 0\n",
    "        res += 'abc'[level]\n",
    "        base *= level\n",
    "        \n",
    "        # 其余字母 两种情况\n",
    "        for i in range(2, n+1):\n",
    "            temp = 2**(n-i)\n",
    "            if k > base+temp:\n",
    "                base += temp\n",
    "                res += 'b' if res[-1] == 'c' else 'c'\n",
    "            else:\n",
    "                res += 'b' if res[-1] == 'a' else 'a'\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    \n",
    "    def dfs_happy_string(self, root: str, result: list[str], max_length: int):\n",
    "        if len(root) == max_length:\n",
    "         result.append(root)\n",
    "\n",
    "        if len(root) < max_length:\n",
    "            if len(root) != 0:\n",
    "                prev = root[-1]\n",
    "            else:\n",
    "                prev = None\n",
    "            if prev is None or prev != 'a':\n",
    "                self.dfs_happy_string(root + 'a', result, max_length)\n",
    "            if prev is None or prev != 'b':\n",
    "                self.dfs_happy_string(root + 'b', result, max_length)\n",
    "            if prev is None or prev != 'c':\n",
    "                self.dfs_happy_string(root + 'c', result, max_length)\n",
    "            \n",
    "\n",
    "\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        result = list()\n",
    "        self.dfs_happy_string(\"\", result, n)\n",
    "        k = k - 1\n",
    "        if k >= len(result):\n",
    "            return \"\"\n",
    "\n",
    "        return result[k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import pow\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        def getchar(idx,prev):\n",
    "            allchars = ['a','b','c']\n",
    "            if not prev: \n",
    "                char = allchars[idx]\n",
    "            else:\n",
    "                allchars.remove(prev)\n",
    "                #print(allchars,idx)\n",
    "                char = allchars[idx]\n",
    "            return char\n",
    "        res = \"\"\n",
    "        if pow(2,n-1)*3<k: return res\n",
    "        prev = None\n",
    "        k -= 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dvr = pow(2,i)\n",
    "            indx = int(k//dvr)\n",
    "            rsd = k%dvr\n",
    "            #print(k, dvr)\n",
    "            cur = getchar(indx,prev)\n",
    "            res += cur\n",
    "            k = rsd\n",
    "            prev = cur\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        tot=0\n",
    "        ans=\"\"\n",
    "\n",
    "        def dfs(s:str, step:int):\n",
    "            nonlocal tot, ans, k\n",
    "\n",
    "            if tot>=k: return\n",
    "\n",
    "            if step==n:\n",
    "                tot+=1\n",
    "#                print(s)\n",
    "                if tot==k:\n",
    "                    ans=s\n",
    "                    return\n",
    "            else:\n",
    "                for ch in ('a','b','c'):\n",
    "                    if (step>0 and ch!=s[-1]) or step==0:\n",
    "                        dfs(s+ch,step+1)\n",
    "\n",
    "        dfs(\"\",0)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getHappyString(self, n: int, k: int) -> str:\r\n",
    "        if k > 3 * 2 ** (n - 1):\r\n",
    "            return ''\r\n",
    "        \r\n",
    "        abcArr = ['a', 'b', 'c']\r\n",
    "        # 储存长度为n的开心字符串\r\n",
    "        deq = collections.deque(['a', 'b', 'c'])\r\n",
    "        for _ in range(n-1):\r\n",
    "            deqLength = len(deq)\r\n",
    "            temp_deq = copy.deepcopy(deq)\r\n",
    "            for s in temp_deq:\r\n",
    "                abcArr.remove(s[-1])\r\n",
    "                deq.append(s + abcArr[0])\r\n",
    "                deq.append(s + abcArr[1])\r\n",
    "                abcArr.append(s[-1])\r\n",
    "            for i in range(deqLength):\r\n",
    "                deq.popleft()\r\n",
    "        \r\n",
    "        deq_sorted = sorted(deq)\r\n",
    "        print(type(deq_sorted))\r\n",
    "        return deq_sorted[k-1]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        if k > 3 * 2 ** (n - 1):\n",
    "            return \"\"\n",
    "        res = \"\"\n",
    "\n",
    "        def dfs(n, k, pre_char):\n",
    "            nonlocal res\n",
    "            if n <= 0 or k <= 0:\n",
    "                return\n",
    "            for char in ['a', 'b', 'c']:\n",
    "                if char == pre_char:\n",
    "                    continue\n",
    "                cnt = 2 ** (n - 1)\n",
    "                if cnt >= k:\n",
    "                    res += char\n",
    "                    dfs(n - 1, k, char)\n",
    "                    return\n",
    "                k -= cnt\n",
    "            return\n",
    "\n",
    "        dfs(n, k, None)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getHappyString(self, n: int, k: int) -> str:\r\n",
    "        if k > 3 * 2 ** (n - 1):\r\n",
    "            return ''\r\n",
    "        \r\n",
    "        base = {\r\n",
    "            'a': ['b', 'c'],\r\n",
    "            'b': ['a', 'c'],\r\n",
    "            'c': ['a', 'b']\r\n",
    "        }\r\n",
    "        # 储存长度为n的开心字符串\r\n",
    "        deq = collections.deque(['a', 'b', 'c'])\r\n",
    "        for _ in range(n-1):\r\n",
    "            deqLength = len(deq)\r\n",
    "            # 迭代对象时不能修改其内容，故采用深复制一个临时栈迭代\r\n",
    "            temp_deq = copy.deepcopy(deq)\r\n",
    "            for s in temp_deq:\r\n",
    "                deq.append(s + base[s[-1]][0])\r\n",
    "                deq.append(s + base[s[-1]][1])\r\n",
    "            for i in range(deqLength):\r\n",
    "                deq.popleft()\r\n",
    "        \r\n",
    "        deq_sorted = sorted(deq)\r\n",
    "        print(type(deq_sorted))\r\n",
    "        return deq_sorted[k-1]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        dq = deque(['a', 'b', 'c'])\n",
    "        depth = 0\n",
    "        result = list()\n",
    "        while dq:\n",
    "            depth += 1\n",
    "            for _ in range(len(dq)):\n",
    "                s = dq.popleft()\n",
    "                if depth == n:\n",
    "                    result.append(s)\n",
    "                else:\n",
    "                    for c in \"abc\":\n",
    "                        if c != s[-1]:\n",
    "                            dq.append(s + c)\n",
    "            if depth == n:\n",
    "                break\n",
    "        return result[k-1] if k <= len(result) else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        res = []\n",
    "        temp = []\n",
    "        candidate = ['a', 'b', 'c']\n",
    "        def dfs(idx):\n",
    "            if len(res) >= k:\n",
    "                return \n",
    "            if idx == n:\n",
    "                res.append(\"\".join(temp))\n",
    "            else:\n",
    "\n",
    "                for c in candidate:\n",
    "                    if not temp or c!= temp[-1]:\n",
    "                        temp.append(c)\n",
    "                        dfs(idx + 1)\n",
    "                        temp.pop()\n",
    "        dfs(0)\n",
    "        if len(res) < k:\n",
    "            return \"\"\n",
    "        else:\n",
    "            return res[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        ret = list()\n",
    "        s = ['a','b','c']\n",
    "        for i in s:\n",
    "            self.backstracting(ret,[i],s,n)\n",
    "        return \"\".join(ret[k-1]) if len(ret) >= k else \"\"\n",
    "\n",
    "    def backstracting(self,ret,ans,s,n):\n",
    "        if len(ans) == n:\n",
    "            ret.append(ans[:])\n",
    "            return\n",
    "        t = ans[-1]\n",
    "        for i in s:\n",
    "            if i == t:\n",
    "                continue\n",
    "            else:\n",
    "                ans.append(i)\n",
    "                self.backstracting(ret,ans,s,n)\n",
    "                ans.pop()\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getHappyString(self, n: int, k: int) -> str:\r\n",
    "        if k > 3 * 2 ** (n - 1):\r\n",
    "            return ''\r\n",
    "        \r\n",
    "        base = {\r\n",
    "            'a': ['b', 'c'],\r\n",
    "            'b': ['a', 'c'],\r\n",
    "            'c': ['a', 'b']\r\n",
    "        }\r\n",
    "        # 储存长度为n的开心字符串\r\n",
    "        deq = collections.deque(['a', 'b', 'c'])\r\n",
    "        for _ in range(n-1):\r\n",
    "            deqLength = len(deq)\r\n",
    "            # 迭代对象时不能修改其内容，故采用深复制一个临时栈迭代\r\n",
    "            temp_deq = copy.deepcopy(deq)\r\n",
    "            for s in temp_deq:\r\n",
    "                deq.append(s + base[s[-1]][0])\r\n",
    "                deq.append(s + base[s[-1]][1])\r\n",
    "            for i in range(deqLength):\r\n",
    "                deq.popleft()\r\n",
    "        \r\n",
    "        # deq_sorted = sorted(deq)\r\n",
    "        # print(type(deq_sorted))\r\n",
    "        return deq[k-1]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getHappyString(self, n: int, k: int) -> str:\r\n",
    "        self.res = ''\r\n",
    "        self.k = k\r\n",
    "        \r\n",
    "        ans = []\r\n",
    "        path = []\r\n",
    "        \r\n",
    "        def back_tracking() -> None:\r\n",
    "            if len(path) == n:\r\n",
    "                ans.append(''.join(path))\r\n",
    "                self.k -= 1\r\n",
    "                if self.k == 0:\r\n",
    "                    self.res = ans[-1]\r\n",
    "                \r\n",
    "                return\r\n",
    "            \r\n",
    "            for char in 'abc':\r\n",
    "                if self.res:\r\n",
    "                    return\r\n",
    "                \r\n",
    "                if path and char == path[-1]:\r\n",
    "                    continue\r\n",
    "                \r\n",
    "                path.append(char)\r\n",
    "                back_tracking()\r\n",
    "                path.pop()\r\n",
    "            \r\n",
    "        back_tracking()\r\n",
    "        \r\n",
    "        return self.res\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        def func(n):\n",
    "            nums = ['a','b','c']\n",
    "            ans = ['a','b','c']\n",
    "            for i in range(1,n):\n",
    "                temp = []\n",
    "                for j in ans:\n",
    "                    for k in nums:\n",
    "                        if j[-1] != k:\n",
    "                            temp.append(j + k)\n",
    "                ans = temp[::]\n",
    "            return ans\n",
    "        \n",
    "        memo = func(n)\n",
    "        return memo[k-1] if len(memo) >= k else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        ans = []\n",
    "        temp = ['a', 'b', 'c']\n",
    "        def traverse(path):\n",
    "            if len(ans) >= k:\n",
    "                return\n",
    "            if len(path) == n:\n",
    "                ans.append(\"\".join(path))\n",
    "                return\n",
    "            for i in range(3):\n",
    "                if len(path) != 0:\n",
    "                    if temp[i] == path[-1]:\n",
    "                        continue\n",
    "                    path.append(temp[i])\n",
    "                    traverse(path)\n",
    "                    path.pop()\n",
    "                else:\n",
    "                    path.append(temp[i])\n",
    "                    traverse(path)\n",
    "                    path.pop()\n",
    "        traverse([])\n",
    "        if len(ans) < k:\n",
    "            return \"\"\n",
    "        return ans[k - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        result = []\n",
    "        abc = ['a','b','c']\n",
    "\n",
    "        def dfs(path):\n",
    "            if len(path) == n:\n",
    "                result.append(path[:])\n",
    "                return\n",
    "            \n",
    "            for i in range(3):\n",
    "                if len(path) > 0 and i == ord(path[-1])-ord('a'):\n",
    "                    continue\n",
    "                path.append(abc[i])\n",
    "                dfs(path)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs([])\n",
    "        return \"\".join(result[k-1]) if len(result) >= k else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        strings = ['a','b','c']\n",
    "        res = []\n",
    "        def dfs(path, total):\n",
    "            if total == 0:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for w in strings:\n",
    "                if len(path) == 0 or w != path[-1]:\n",
    "                    path += w\n",
    "                    dfs(path, total-1)\n",
    "                    path.pop()\n",
    "\n",
    "        dfs([], n)\n",
    "        res.sort()\n",
    "        if len(res) < k:\n",
    "            return ''\n",
    "        return ''.join(res[k-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        strings = ['a','b','c']\n",
    "        res = []\n",
    "        def dfs(path, total):\n",
    "            if total == 0:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            idx = 0\n",
    "            for w in strings:\n",
    "                if len(path) == 0 or w != path[-1]:\n",
    "                    path += w\n",
    "                    dfs(path, total-1)\n",
    "                    idx += 1\n",
    "                    path.pop()\n",
    "\n",
    "        dfs([], n)\n",
    "        res.sort()\n",
    "        # print(res)\n",
    "        if len(res) < k:\n",
    "            return ''\n",
    "        return ''.join(res[k-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        ans = []\n",
    "        path = []\n",
    "        charset = ['a', 'b', 'c']\n",
    "        def dfs(m):\n",
    "            if m == n:\n",
    "                ans.append(\"\".join(path[:]))\n",
    "                return\n",
    "            for i in range(len(charset)):\n",
    "                if (len(path) >= 1 and\n",
    "                    charset[i] == path[-1]):\n",
    "                    continue\n",
    "                path.append(charset[i])\n",
    "                dfs(m + 1)\n",
    "                path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        if len(ans) < k:\n",
    "            return \"\"\n",
    "        else:\n",
    "            return ans[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        # def func(n):\n",
    "        #     nums = ['a','b','c']\n",
    "        #     ans = ['a','b','c']\n",
    "        #     for i in range(1,n):\n",
    "        #         temp = []\n",
    "        #         for j in ans:\n",
    "        #             for k in nums:\n",
    "        #                 if j[-1] != k:\n",
    "        #                     temp.append(j + k)\n",
    "        #         ans = temp[::]\n",
    "        #     return ans\n",
    "\n",
    "        chars = ['a','b','c']\n",
    "        ans = []\n",
    "        \n",
    "        def back(nums:str):\n",
    "            if len(nums) == n:\n",
    "                ans.append(nums)\n",
    "                return \n",
    "            for i in chars:\n",
    "                if not nums or nums[-1] != i:\n",
    "                    back(nums + i)\n",
    "        \n",
    "        back('')\n",
    "        return ans[k-1] if len(ans) >= k else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        ans = []\n",
    "        path = []\n",
    "        \n",
    "        def back_tracking() -> None:\n",
    "            if len(path) == n:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            \n",
    "            for char in 'abc':\n",
    "                if path and char == path[-1]:\n",
    "                    continue\n",
    "                \n",
    "                path.append(char)\n",
    "                back_tracking()\n",
    "                path.pop()\n",
    "            \n",
    "        back_tracking()\n",
    "        \n",
    "        if len(ans) < k:\n",
    "            return ''\n",
    "        else:\n",
    "            return ans[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        output = []\n",
    "        candi = ['a','b','c']\n",
    "        def dfs(s, res):\n",
    "            if res == 0:\n",
    "                output.append(s)\n",
    "                return\n",
    "            for zimu in candi:\n",
    "                if s and s[-1] == zimu:\n",
    "                    continue\n",
    "                dfs(s+ zimu,res-1)\n",
    "        dfs(\"\", n)\n",
    "        output.sort()\n",
    "        if len(output) < k:\n",
    "            return \"\"\n",
    "        return output[k-1]\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        s = 'abc'\n",
    "        total_combine = set()\n",
    "\n",
    "        def dfs(curr):\n",
    "            if len(curr) == n:\n",
    "                total_combine.add(curr)\n",
    "                return\n",
    "            for ch in s:\n",
    "                if curr[-1] != ch:\n",
    "                    dfs(curr+ch)\n",
    "\n",
    "        for ch in s:\n",
    "            dfs(ch)\n",
    "\n",
    "        total_combine = sorted(list(total_combine))\n",
    "        return total_combine[k-1] if len(total_combine) >= k else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        ans = []\n",
    "        def dfs(index,stack):\n",
    "            nonlocal k\n",
    "            if index == n:\n",
    "                #print(f'第{k}次 {stack}')\n",
    "                ans.append(''.join(stack))\n",
    "                return stack\n",
    "            res = ''\n",
    "            for s in 'abc':\n",
    "                if stack and stack[-1] == s:\n",
    "                    continue\n",
    "                res = dfs(index+1,stack+[s])\n",
    "            return res\n",
    "        dfs(0,[])\n",
    "        #print(ans,len(ans))\n",
    "        return ans[k-1] if len(ans) > k - 1 else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        chars = ['a', 'b', 'c']\n",
    "        ans = []\n",
    "        def back(cur):\n",
    "            if len(cur) == n:\n",
    "                ans.append(cur)\n",
    "                return\n",
    "            for c in chars:\n",
    "                if not cur or cur[-1] != c:\n",
    "                    back(cur + c)\n",
    "        back('')\n",
    "        if len(ans) < k:\n",
    "            return ''\n",
    "        return ans[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        total = pow(2, n - 1) * 3\n",
    "        if k > total:\n",
    "            return ''\n",
    "        s, res = '', []\n",
    "        def find_all(cnt):\n",
    "            nonlocal s \n",
    "            if cnt > n:\n",
    "                res.append(s[:])\n",
    "                return \n",
    "            for c in ['a', 'b', 'c']:\n",
    "                if len(s) == 0 or c != s[-1]:\n",
    "                    s += c\n",
    "                    find_all(cnt + 1)\n",
    "                    s = s[:-1]\n",
    "        find_all(1)\n",
    "        return res[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        happy_strings = []\n",
    "        \n",
    "        def generate_strings(s):\n",
    "            if len(s) == n:\n",
    "                happy_strings.append(s)\n",
    "                return\n",
    "            for c in ['a', 'b', 'c']:\n",
    "                if not s or s[-1] != c:\n",
    "                    generate_strings(s + c)\n",
    "        \n",
    "        generate_strings('')\n",
    "        if len(happy_strings) < k:\n",
    "            return \"\"\n",
    "        else:\n",
    "            return happy_strings[k-1]\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        happy_strings = []\n",
    "        \n",
    "        def generate_strings(s):\n",
    "            if len(s) == n:\n",
    "                happy_strings.append(s)\n",
    "                return\n",
    "            for x in ['a', 'b', 'c']:\n",
    "                if not s or s[-1] != x:\n",
    "                    generate_strings(s + x)\n",
    "        \n",
    "        generate_strings('')\n",
    "        if len(happy_strings) < k:\n",
    "            return \"\"\n",
    "        else:\n",
    "            return happy_strings[k-1]\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        def dfs(path, last):\n",
    "            if len(path) == n:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for c in ['a', 'b', 'c']:\n",
    "                if c == last: continue\n",
    "                dfs(path+c, c)\n",
    "        res = []\n",
    "        dfs(\"\", \"\")\n",
    "        \n",
    "        return res[k-1] if k <= len(res) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        ans=[]\n",
    "        \n",
    "        \n",
    "        def dfs(current):\n",
    "            if len(current)==n:\n",
    "                ans.append(current)\n",
    "                return\n",
    "            for i in ['a','b','c']:\n",
    "                if not current or i!=current[-1]:\n",
    "                    dfs(current+i)\n",
    "                    \n",
    "                    \n",
    "        dfs('')\n",
    "        if len(ans)<k:\n",
    "            return ''\n",
    "        return ans[k-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "\n",
    "\n",
    "        res = []\n",
    "        def dfs(s):\n",
    "            if len(s) == n:\n",
    "                res.append(s)\n",
    "                return\n",
    "\n",
    "            for x in ['a', 'b', 'c']:\n",
    "                if not s or s[-1] != x:\n",
    "                    dfs(s + x)\n",
    "\n",
    "\n",
    "        dfs(\"\")\n",
    "        if len(res) < k:\n",
    "            return ''\n",
    "\n",
    "        else :\n",
    "            return res[k - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getHappyString(self, n: int, k: int) -> str:\n",
    "        def dfs(path):\n",
    "            if len(path) == n:\n",
    "                ans.append(\"\".join(path))\n",
    "                return\n",
    "            for c in ['a', 'b', 'c']:\n",
    "                if path and path[-1] == c:\n",
    "                    continue\n",
    "                path.append(c)\n",
    "                dfs(path)\n",
    "                path.pop()\n",
    "        \n",
    "        ans = []\n",
    "        dfs([])\n",
    "        if len(ans) < k:\n",
    "            return \"\"\n",
    "        ans.sort()\n",
    "        return ans[k - 1]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
